/*
 * heuristicGenerator.c
 *
 *  Created on: Oct 1, 2013
 * @author Daniel Rogers
 */

#include "heuristicGenerator.h"

#define CUBE_CORNER_BUCKETS (CORNER_SLOTS * 2)
#define CUBE_EDGE_BUCKETS (EDGE_SLOTS * 2)
// WARNING: The memory usage of the edge map will initially be
// (((12! / 6!) * 2^6 * CUBE_EDGE_INITIAL * 13) / 2^30) GB,
// plus an additional (((12! / 6!) * 2^6 * 2) / 2^30) GB
#define CUBE_EDGE_INITIAL 1
#define CUBE_EDGE_GROWTH 1

bool generateTables()
{
    //pointers to storage for the tables
    //3 uint8_t pointers for tables in order, corner, edge1, edge2
    uint8_t * htables[3];

    //Data for calculating permutations
    bool succeeded = true;

    //Queue for storing states to explore next
    Queue queue;

    //Table index temporary storage
    uint32_t indexes[3];

    //Retrieved distance temp storage
    //Misc
    uint8_t j;

    Cube base;
    //Get the start(goal) state
    getUnitCube(&base);
    initQueue(&queue);

    //Set up the queue of states to expand, starting with initial state
    //  @ layer 0
    enq(&queue, base, 0);

    /*
     * Allocate memory to store tables
     */
    htables[0] = calloc(CORNER_SLOTS, sizeof(uint8_t));
    htables[1] = calloc(EDGE_SLOTS, sizeof(uint8_t));
    htables[2] = calloc(EDGE_SLOTS, sizeof(uint8_t));

    //Set the distance of the first state to 0xF to simplify logic inside
    //  while loop
    getCodedIndexes(&base, indexes);
    for (j = 0; j < 3; ++j)
    {
        storeHeuristic(htables[j], indexes[j], 0xF);
    }

    //Generate the edge tables
    generateEdges(htables, &queue);

    //Re-init the queue
    initQueue(&queue);
    enq(&queue, base, 0);

    //Generate the corner table
    generateCorners(htables, &queue);

    //Reset distance of unit cube to 0
    getUnitCube(&base);
    getCodedIndexes(&base, indexes);
    for (j = 0; j < 3; ++j)
    {
        storeHeuristic(htables[j], indexes[j], 0);
    }

    /*
     * Write tables out to file
     */
    FILE * cfile;
    FILE * efile1;
    FILE * efile2;

    cfile = fopen("corner_table.bin", "wb+");
    efile1 = fopen("edge_table1.bin", "wb+");
    efile2 = fopen("edge_table2.bin", "wb+");

    if (!cfile || !efile1 || !efile2)
    {
        puts("Unable to open a table file for writing");
        succeeded = false;
    }
    else
    {
        fwrite(htables[0], sizeof(uint8_t), CORNER_SLOTS, cfile);
        fwrite(htables[1], sizeof(uint8_t), EDGE_SLOTS, efile1);
        fwrite(htables[2], sizeof(uint8_t), EDGE_SLOTS, efile2);

        fclose(cfile);
        fclose(efile1);
        fclose(efile2);
    }

    /*
     * Free allocated memory
     */
    free(htables[0]);
    free(htables[1]);
    free(htables[2]);

    return (succeeded);
}

//Uses ~500 of memory @ max size w/ compressed cubes in queue
//Uses ~680 meg of memory @ max size w/o compressed cubes
void generateCorners(uint8_t * htables[3], Queue * queue)
{
    //Current depth tracker
    uint8_t dist;
    //Current state to expand
    Cube current;
    Cube perms[18];

    //Cube indexes
    uint32_t indexes[3];
    uint8_t distances[3];

#ifdef DEBUG
    //Last seen
    uint8_t last_dist = 0;
    //timer to output
    uint16_t ticker = 0;
    //Number of states created
    uint32_t enums = 0;
    //Size of queue currently
    uint32_t queue_size = 1;
#endif

    /*
     * Enumerate all corner cubie states
     */
    do
    {
        //get layer
        dist = queue->head->layers[queue->head->start_pos] + 1;
#ifdef DEBUG
        if (last_dist != dist)
        {
            printf("corners at layer: %d\n", dist);
            last_dist = dist;
            printf("    queue-size: %d\n", queue_size);
            printf("    cur-enums: %d\n", enums);
        }
        ++ticker;
        if (ticker == 0)
        {
            printf("corner clock at layer: %d\n", dist);
            printf("    queue-size: %d\n", queue_size);
            printf("    cur-enums: %d\n", enums);
        }

        --queue_size;
#endif
        //Get the next state to expand
        current = deq(queue);

        //Expand the state, Korf uses the face turn definition of a move,
        permuteAllFaces(current, perms);

        //Record entries, and enqueue for later expansion
        for (uint8_t i = 0; i < 18; ++i)
        {
            //Get table indexes
            getCodedIndexes(&perms[i], indexes);

            //Get already stored values
            getHeuristics(htables, indexes, distances);

            //See if already explored, skip this iteration if so
            if (!distances[0])
            {
                //Queue it to expand later
                enq(queue, perms[i], dist);
                //Record the seen state
                storeHeuristic(htables[0], indexes[0], dist);
#ifdef DEBUG
                ++queue_size;
                ++enums;
#endif
            }
        } /** end permutation for **/
    } while (!isEmpty(queue));
}

//From testing on laptop
//  Without compressed keysets & compressed queue, able to expand:
//      ~37 million nodes generated in 5 gigs of memory
//  With compression:
//      ~46 million nodes generated in 5 gigs of memory
//The BFS part of the generation caps out @ 4gigs of memory w/ ~97million
//  nodes queued for expansion, leaving ~400,000,000,000 for the DFS
void generateEdges(uint8_t * htables[3], Queue * queue)
{
    //Current depth tracker
    uint8_t dist;
    //Current state to expand
    Cube current;
    Cube perms[18];

    //Cube indexes
    uint32_t indexes[3];
    uint8_t distances[3];

    //Hash table, indexed by edge1, storing an array of edge2 values
    EdgekeySet ** explored_states = malloc(
    CUBE_EDGE_BUCKETS * sizeof(EdgekeySet*));
    //Used to grow the vectors in the hash table
    uint16_t * states_ar_lens = malloc(CUBE_EDGE_BUCKETS * sizeof(uint16_t));

    initEdgeTable(explored_states, states_ar_lens);

#ifdef DEBUG
    //Last seen
    uint8_t last_dist = 0;
    //timer to output
    uint16_t ticker = 0;
    //Number of states created
    uint32_t enums = 0;
    //Number of items in the queue
    uint32_t queue_size = 1;
#endif

    /*
     * Enumerate all edge cubie states
     */
    do
    {
        //get layer
        dist = queue->head->layers[queue->head->start_pos] + 1;

#ifdef DEBUG
        if (last_dist != dist)
        {
            printf("edges at layer: %d\n", dist);
            last_dist = dist;

            printf("    queue-size: %d\n", queue_size);
            printf("    cur-enums: %d\n", enums);
        }
        ++ticker;
        if (ticker == 0)
        {
            printf("edge clock at layer: %d\n", dist);
            printf("    queue-size: %d\n", queue_size);
            printf("    cur-enums: %d\n", enums);
        }

        --queue_size;
#endif

        //don't start expanding depth 8
        if (dist == 8)
        {
            break;
        }

        //Get the next state to expand
        current = deq(queue);

        //Expand the state, Korf uses the face turn definition of a move,
        permuteAllFaces(current, perms);

        //Record entries, and enqueue for later expansion
        for (uint8_t i = 0; i < 18; ++i)
        {
            //Get table indexes
            getCodedIndexes(&perms[i], indexes);

            //See if already explored, skip this iteration if so
            // edgeTableContains will return true if there is a mapping from
            //  index1->index2. If there is not, the table will be updated
            if (!equalCubes(&perms[i], &UNIT_CUBE)
                    && !edgeTableContains(explored_states, states_ar_lens,
                            indexes[1], indexes[2]))
            {
                //Get already stored values
                getHeuristics(htables, indexes, distances);

                if (dist < 10)
                {
                    //Queue it to expand later
                    enq(queue, perms[i], dist);
#ifdef DEBUG
                    ++queue_size;
#endif
                }

                if (!distances[1])
                {
                    storeHeuristic(htables[1], indexes[1], dist);
#ifdef DEBUG
                    ++enums;
#endif
                }
                if (!distances[2])
                {
                    storeHeuristic(htables[2], indexes[2], dist);
#ifdef DEBUG
                    ++enums;
#endif
                }
            }
        } /** end permutation for **/
    } while (!isEmpty(queue));

    //Free up used space for tables
    freeEdgeTable(explored_states, states_ar_lens);

#ifdef DEBUG
    uint8_t ticker2 = 0;
#endif

    //DFS the rest
    while (!isEmpty(queue))
    {
        //All of depth 7 queued
        //Get next @ depth 7
        current = deq(queue);
        --queue_size;
        //DFS it, we are @ depth 7, next is 8, have all perms @ 7
        //  So start at 8 and go to 10
        recurseExpand(htables, &current, &UNIT_CUBE, &UNIT_CUBE, 8, 10);

#ifdef DEBUG
        ++ticker2;
        if (ticker2 == 0)
        {
            printf("DFS @ 8 remaining queue-size: %d\n", queue_size);
        }
#endif
    }
}

void recurseExpand(uint8_t * htables[3], Cube * current,
        const Cube * const prev, const Cube * const prev2, uint8_t depth,
        uint8_t limit)
{
    //Next states to expand
    Cube perms[18];
    permuteAllFaces(*current, perms);
    uint32_t indexes[3];
    uint8_t distances[3];

    for (uint8_t i = 0; i < 18; ++i)
    {
        //Cut out wasted work
        if (!equalCubes(&perms[i], prev) && !equalCubes(&perms[i], prev2))
        {
            //Get table indexes
            getCodedIndexes(&perms[i], indexes);
            //Get already stored values
            getHeuristics(htables, indexes, distances);

            //Better depth for edge 1, or unset
            if (distances[1] > depth || !distances[1])
            {
                storeHeuristic(htables[1], indexes[1], depth);
            }
            //Better depth for edge 2, or unset
            if (distances[2] > depth || !distances[2])
            {
                storeHeuristic(htables[2], indexes[2], depth);
            }

            if (depth < limit)
            {
                recurseExpand(htables, &perms[i], current, prev, depth + 1,
                        limit);
            }
        }
    }

}

void storeHeuristic(uint8_t * htable, const uint32_t index, uint8_t dist)
{
    uint8_t temp;
    //even indexes go in bottom 4 bits, odd in top 4 bits
    //  -> even == 0x0F, odd == 0xF0
    uint8_t shf = (index % 2) * 4;
    //Need to save 0xF0 if even (%2 == 0), 0x0F if odd (%2 == 1)
    uint8_t mask = 0xF0 >> shf;

    //Stored in 8bit pairs
    temp = dist << shf;
    htable[index / 2] &= mask; //clear bits to be set
    htable[index / 2] |= temp; //OR combine bits
}

bool edgeTableContains(EdgekeySet ** table, uint16_t * lens, uint32_t index,
        uint32_t key)
{
    EdgekeySet * cell = table[index];
    uint16_t len = lens[index];
    uint16_t i;
    //the extracted key
    uint32_t cellkey = 0;

    for (i = 0; i < len; ++i)
    {
        cellkey = extractKey(&cell[i / KEYS_PER_SET], i % KEYS_PER_SET);
        if (cellkey == key)
        {
            return (true);
        }
        //We might compare against empty cells, that have been set to maxvalue
        //  We want to exit early if this is the case, so we don't increment
        //  space size incorrectly.
        if (cellkey == 0x3FFFFFF)
        {
            break;
        }
    }

    //If we didn't find the key, append it to the table
    if (i == len)
    {
        //Didn't break early, so array is full, Resize the array
        len += (CUBE_EDGE_GROWTH * KEYS_PER_SET);
        //This might fail
        EdgekeySet * newcell = realloc(cell, len * sizeof(EdgekeySet));
        if (newcell)
        {
            cell = newcell;
        }
        else
        {
            //failure in realloc
        }
        //Record new size
        lens[index] = len;
        //Set the memory to 0xFF so compares will not generate false
        //  positives, and we can test for empty cells
        memset(&cell[i / KEYS_PER_SET], 0xFF, sizeof(EdgekeySet));
        table[index] = cell;
    }

    //Store value in array
    insertKey(&cell[i / KEYS_PER_SET], key, i % KEYS_PER_SET);

    return (false);
}

uint32_t extractKey(EdgekeySet * set, uint8_t loc)
{
    uint32_t key;

    switch (loc)
    {
    case 0:
        //Getting first 26 bits
        //  high 2 bits are in array [3], high 2
        //  Out of place by 6 bits so
        //  shift by 26 - 2 - 6, 18
        key = (set->keys[3] & 0xC0) << 18;
        //  second highest 8 are in array[4]
        //  shift by 26 - 10, 16
        key |= (set->keys[2] << 16);
        key |= (set->keys[1] << 8);
        key |= (set->keys[0]);
        break;
    case 1:
        //Getting next 26 bits
        //  High 4 bits is in high 4 of array [6]
        //  out of place by 4 bits so
        //  shift by 26 - 4 - 4, 18
        key = (set->keys[6] & 0xF0) << 18;
        //Next bytes
        key |= (set->keys[5] << 14);
        key |= (set->keys[4] << 6);
        //Lowest 6 bits are in low 6 bits of array[3]
        key |= (set->keys[3] & 0x3F);
        break;
    case 2:
        //Getting 3rd set of 26
        //  High 6 bits in high 6 of array[9]
        //  Out of place by 2 so
        //  shift by 26 - 6 - 2, 18
        key = (set->keys[9] & 0xFC) << 18;
        //Next bytes
        key |= (set->keys[8] << 12);
        key |= (set->keys[7] << 4);
        //Lowest 4 bits in low 4 bits of array[6]
        key |= (set->keys[6] & 0xF);
        break;
    default:
        //Getting last set of 26
        //  High byte in array[12]
        //  Shift by 26 - 8, 18
        key = (set->keys[12] << 18);
        //Next bytes
        key |= (set->keys[11] << 10);
        key |= (set->keys[10] << 2);
        //Lowest 2 bits in low 2 of array[9]
        key |= (set->keys[9] & 0x3);
    }

    return (key);
}

void insertKey(EdgekeySet * set, uint32_t key, uint8_t loc)
{
    switch (loc)
    {
    case 0:
        //Setting first 26 bits
        //Nothing special for first 2 bytes
        set->keys[0] = key & 0xFF;
        key >>= 8;
        set->keys[1] = key & 0xFF;
        key >>= 8;
        set->keys[2] = key & 0xFF;
        //Shift over by 6, since we want to be 8-2 from end of cell
        //  for store
        key >>= 6;
        //Store high 2 bits of key in high 2 of array[3]
        //Clear high 2 then OR in keyval
        set->keys[3] &= 0x3F;
        set->keys[3] |= (key & 0xC0);
        break;
    case 1:
        //Setting next 26 bits
        //Lowest 6 bits go in low 6 bits of array[3]
        //Clear then OR in keyval
        set->keys[3] = key & 0x3F;
        key >>= 6;
        //Next 2 bytes
        set->keys[4] = key & 0xFF;
        key >>= 8;
        set->keys[5] = key & 0xFF;
        //Shift over by 4 since we want to be 8-4 from end of cell
        //  for store
        key >>= 4;
        //High 4 bits is in high 4 of array [6]
        //Clear high4 then OR in keyval
        set->keys[6] &= 0x0F;
        set->keys[6] |= (key & 0xF0);
        break;
    case 2:
        //Setting 3rd set of 26
        //  lowest 4 bits in low 4 bits of array[6]
        //Clear low4 then OR in keyval
        set->keys[6] &= 0xF0;
        set->keys[6] |= (key & 0x0F);
        key >>= 4;
        //Next 2 bytes
        set->keys[7] = key & 0xFF;
        key >>= 8;
        set->keys[8] = key & 0xFF;
        //Want to be 8-6 bits from the end so shift by 2
        key >>= 2;
        //High 6 bits go in high 6 of array[9]
        //Clear high 6 OR in keyval
        set->keys[9] &= 0x03;
        set->keys[9] |= (key & 0xFC);
        break;
    default:
        //Setting last set of 26
        //Lowest 2 bits in low 2 of array[9]
        //clear low 2 and OR in keyval
        set->keys[9] &= 0xFC;
        set->keys[9] |= (key & 0x03);
        key >>= 2;
        //Next 3 bytes
        set->keys[10] = key & 0xFF;
        key >>= 8;
        set->keys[11] = key & 0xFF;
        key >>= 8;
        set->keys[12] = key & 0xFF;
    }
}

void initEdgeTable(EdgekeySet ** table, uint16_t * lens)
{
    //Set up initial lengths
    for (uint32_t i = 0; i < CUBE_EDGE_BUCKETS; ++i)
    {
        //Set the initial size, remember there are multiple keys per set
        lens[i] = CUBE_EDGE_INITIAL * KEYS_PER_SET;
        //Make the table cell
        table[i] = malloc(CUBE_EDGE_INITIAL * sizeof(EdgekeySet));
        //Set all bytes to 0xFF so no false positives will be genned
        memset(table[i], 0xFF, (CUBE_EDGE_INITIAL) * sizeof(EdgekeySet));
    }
}

void freeEdgeTable(EdgekeySet ** table, uint16_t * lens)
{
    free(lens);
    for (uint32_t i = 0; i < CUBE_EDGE_BUCKETS; ++i)
    {
        free(table[i]);
    }
    free(table);
}
